/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int n = preorder.size();
        if (n <= 0) {
            return NULL;
        }

        map<int, int> indexMap;
        for (int i = 0; i < n; ++i) {
            indexMap[inorder[i]] = i;
        }
        return buildHelper(preorder, 0, inorder, 0, n, indexMap);
    }

    TreeNode *buildHelper(const vector<int> &preorder, int preStart,
                          const vector<int> &inorder, int inStart,
                          int len,
                          map<int, int> &indexMap) {
        if (len <= 0) {
            return NULL;
        }
        int val = preorder[preStart];
        int pos = indexMap[val];
        int leftLen = pos - inStart;
        int rightLen = len - leftLen - 1;

        TreeNode *node = new TreeNode(val);
        node->left = buildHelper(preorder, preStart + 1,
                                 inorder, inStart,
                                 leftLen, indexMap);
        node->right = buildHelper(preorder, preStart + 1 + leftLen,
                                  inorder, inStart + leftLen + 1,
                                  rightLen, indexMap);
        return node;
    }
};
